# 下一个更大元素II：https://leetcode-cn.com/problems/next-greater-element-ii/

# 暴力破解，竟然能过， 花了2632毫秒~~~
class Solution:
    def nextGreaterElements(self, nums: list) -> list:
        """
            暴力破解: 每个元素可以比较 n-1次， 循环取模
        """
        rst = []
        n = len(nums)
        for i in range(n):
            num = nums[i]
            for j in range(i+1, i + n):
                if num < nums[j%n]:
                    rst.append(nums[j%n])
                    break
            else:
                rst.append(-1)
        
        return rst


# 单调栈
class Solution:
    def nextGreaterElements(self, nums: list) -> list:
        """
            单调栈，与暴力解法相同，取模一下。 但是和 下一个更大元素I,不同的是， 这里进栈的不在是元素值，而是元素下标！ 
            因为元素是重复的，所以进下标，就可以判断该下标的取值了。
        """
        n = len(nums)
        rst = [-1] * n
        stack = []
        for i in range(2*n - 1):
            index = i % n
            if not stack or nums[index] < nums[stack[-1]]:
                stack.append(index)
            else:
                while stack and nums[index] > nums[stack[-1]]:
                    rst[stack.pop()] = nums[index]
                stack.append(index) 

        # 找不到的默认就是 -1了
        return rst
            

# 官方简洁诶写法（if else）
class Solution:
    def nextGreaterElements(self, nums: list) -> list:
        n = len(nums)
        ret = [-1] * n
        stk = list()

        for i in range(n * 2 - 1):
            while stk and nums[stk[-1]] < nums[i % n]:
                ret[stk.pop()] = nums[i % n]
            stk.append(i % n)
        
        return ret

